package com.mxw.算法之美.a6排序;

/**
 * @author Administrator
 * @create 2024/7/26 10:17
 */
public class a06LinearSort {
    /**
     线性排序： 桶排序，计数排序，基数排序

     桶排序：排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的。
     条件：
        桶与桶之间有着天然的大小顺序。每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
        桶分布比较均匀。
        适合用在外部排序中：数据量比较大，内存有限，无法将数据全部加载到内存中。
     举例：10GB的订单数据，内存只有几百MB，订单数据按照订单金额进行排序。
        扫描一遍文件，将所有的订单根据金额划分到100个桶里。第一个桶存放1-100之间的订单，第二个桶存放101-200之间的订单，依次类推。每个桶对应一个文件。订单被均匀的划分到100个文件中，每个小文件大约100MB
        可以将100个小文件一次放到内存中，用快排来排序。等所有文件排好序之后，再把排序好的小文件合并成一个大的文件。

     计数排序：考生名次。


     排序选择：
        小规模的数据，选择时间复杂度0(n2);大规模的数据，选择时间复杂度0(nlogN)

     C语言的qSort()根据数量规模动态采用不同的排序算法
     元素个数小于4，用插入排序。然后使用归并排序，空间换时间，数据规模再大，用快速排序。

     */
}
